#ifndef _QSORT_H_
#define _QSORT_H_

#include <cmath>
#include <stdio.h>

/* Sorting an array in ascending order
int* beg - pointer to beginning of the array
int* end - pointer to ending of the array
*/
template <class Cmp, class T>
void quicksort (T* beg, T* end, Cmp cmp)
{
  size_t size = end - beg;
  if ( (size == 0) || (size == 1) )
    return;   
      
  T* med = beg + (end - beg)/2; // median element
  T* left = beg; // left pointer
  T* right = end - 1; // right pointer
  T temp;
  
  while (left != right)
  {
    while ( cmp(med, left, 1) && (left != med) )
      ++left;
    while ( cmp(right, med, 0) )
	  --right;

    temp = *left;
    *left = *right;
    *right = temp;
    if (left == med)
    med = right;
    else if (right == med)
    med = left;
  }
  if (beg < (med-1)) quicksort(beg, med, cmp);
  if (end > (med+1)) quicksort(med+1, end, cmp);  
}

#endif